Programmable logic devices (PLDs) may be configured to implement a variety of user designs. A programmable logic device may include programmable logic resources and programmable interconnect resources. Logic components of a user design may be mapped to the programmable logic resources and connections between the mapped logic components may be routed through the programmable interconnect resources.
The programmable logic resources of a PLD may include look-up tables (LUTs). An example LUT may have four 1-bit input signals and one 1-bit output signal, and may be configured to implement any logic function of four or fewer inputs. For example, the LUT may be configured to implement the function of a 4-input NAND gate, a 4-input OR gate, a 4-input XOR gate, or a 3-input AND gate. Thus, for a specific logic component of a user design that is a function of up to four inputs, the implementation of the user design may map the specific logic component to a particular LUT of the PLD.
The programmable interconnect resources of the PLD may connect the logic components of the user design that are mapped to the programmable logic resources. After the logic components of the user design are mapped to the programmable logic resources of the PLD, connections between the logic components in the programmable logic resources may be routed through the programmable interconnect resources.
In one heuristic approach for routing a mapped user design, a first phase may route each connection through the programmable interconnect resources without regard to whether each programmable interconnect resource is already used by another connection. A second phase of routing may eliminate any overlapping usage by multiple connections of a programmable interconnect resource.
A cost function may be used during the elimination of overlapping usage of the programmable interconnect resources. The cost function may, for example, be primarily based on a predicted operating frequency for the implementation of the design in the programmable logic device. A contribution to the cost function may be gradually increased for each programmable interconnect resource with overlapping usage. After each such increase, the implementation may be incrementally modified to reduce the cost function, and these incremental modifications will tend to eliminate overlapping resource usage. The routing may be completed when the gradual increase in the cost of overlapping resources causes the incremental modification to eliminate all of the overlapping usage of the programmable interconnect resources.
Overlap removal is a heuristic that tends to eliminate overlapping usage by multiple connections of programmable interconnect resources by moving the less timing critical connections to other programmable interconnect resources. Because heuristics are used in this approach to generating an implementation of a user design, further improvements of the implementation are frequently possible.
The present invention may address one or more of the above issues.